1. Field of the Invention
The invention is related to the field of communication systems, and in particular, to a packet scheduling system that schedules packet transmission according to a hierarchy of tunnels.
2. Statement of the Problem
A packet communication system transfers packets within data streams between customer sites. The packets contain information, such as voice, video, and data. The data streams are often grouped into data tunnels to simplify management. Thus, a data tunnel is a group of data streams that flow between two customer sites. For example, a business with offices in San Francisco and New York may have a data tunnel between San Francisco and New York that includes a group of data streams. The data streams are distinguished from one another by identifiers in the packets.
The packet communication system uses various service classes to define the data streams within the tunnel. For Asynchronous Transfer Mode (ATM) communications, service classes have been defined for Constant Bit Rate (CBR), Variable Bit Rate (VBR), Available Bit Rate (ABR), Unspecified Bit Rate (UBR), and Guaranteed Flat Rate (GFR). The service class for a data stream is typically selected based on the type of data being transferred.
The packet communication system uses a scheduling system to determine when to transfer packets for the respective data streams within the tunnel. Packet scheduling is primarily based on service class. For example, a CBR data stream typically gets priority scheduling over an ABR bit stream.
Currently, CBR tunnels are available that carry CBR, VBR, ABR, GFR, and UBR data streams. Unfortunately, CBR tunnels can be inefficient or costly because constant bandwidth is allocated to the tunnel and may go unused. In addition, multiple tunnels with different service classes require a scheduling system for the tunnels in addition to the data streams. Current tunnel scheduling systems combine tunnel and data stream scheduling into a single scheduling table. The single scheduling table precludes complex scheduling and is not scalable.
A scheduling system is needed that supports tunnels that comprise multiple service classes. The scheduling system should allow for complex and hierarchical scheduling. The scheduling system should be scalable.
The invention solves the above problems with a packet scheduling system for a packet communication network. The packet scheduling system supports tunnels that use multiple service classes, such as CBR, VBR, ABR, GFR, and UBR. Advantageously, the bit rate of the tunnels may vary dynamically to optimize bandwidth utilization. The packet scheduling-system allows for a hierarchical scheduling arrangement among multiple tunnels.
In some embodiments of the invention, a packet communication scheduling system comprises three tunnel schedulers, a packet scheduler, and a rate controller. The packet scheduler generates a packet schedule and first-set information in response to packet information. The first tunnel scheduler generates a first schedule for a first set of tunnels in response to the first-set information. The first tunnel scheduler also generates second-set information in response to the first-set information. The second tunnel scheduler generates a second schedule for a second set of tunnels in response to the second-set information. The second tunnel scheduler also generates third-set information in response to the second-set information. The third tunnel scheduler generates a third schedule for a third set of tunnels in response to the third-set information. The feedback loop rate controller receives and distributes packet system feedback information. The tunnel schedulers also generate their respective schedules in response to the packet system feedback information.
The third tunnel scheduler selects a next third-set tunnel identifier based on the third schedule. The second tunnel scheduler selects a next second-set tunnel identifier based on the second schedule and the next third-set tunnel identifier. The first tunnel scheduler selects a next first-set tunnel identifier based on the first schedule and the next second-set tunnel identifier. The packet scheduler selects a next packet identifier for a next packet transmission based on the next first-set tunnel identifier and the packet schedule.